// https://www.lintcode.com/problem/rotate-list/my-submissions

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: the List
     * @param k: rotate to the right k places
     * @return: the list after rotation
     */
    ListNode * rotateRight(ListNode * head, int k) {
        if(!head) return head;
        ListNode * fast = head;
        ListNode * slow = head;
        int len = 0;
        while (fast) 
        {
            fast = fast->next;
            len++;
        }
        k = k % len;
        fast = head;
        for (int i = 0; i < k; ++i) fast = fast->next;
        while (fast->next)
        {
            fast = fast->next;
            slow = slow->next; 
        }
        fast->next = head;
        head = slow->next;
        slow->next = NULL;
        
        return head;
    }
};